/**
 * 
 */

/**
 * @author 
 * Yannic Remmet			196983
 * Tobias Trabelsi			197112
 * Anna-Katharina Wickert	197122
 */
import java.util.ArrayList;



public class SearchTree<T extends Comparable<? super T>> extends BinaryTree<T>{
	private String nNFError = "I was'nt able to find an Node thats equals to : ";
	private String nNError = "No NULL Objects in this Tree!";
	SearchTree(){
		super();
	}
	SearchTree(TreeNode<T> a){
		super(a);
	}
	SearchTree(T a){
		this(new TreeNode<T>(a));
	}
	public TreeNode<T> insert(T o){
		if (o != null)
			return super.insert(o);
		throw new UnsupportedOperationException(nNError);
	}
	public TreeNode<T> insert(TreeNode<T> o){
		if (o != null)
			return super.insert(o);
		throw new UnsupportedOperationException(nNError);
	}
	public int level(T o) throws NodeNFException{
		TreeNode<T> help = super.getRoot();
		int i = 0;
		if( o == null){
			throw new NodeNFException(nNError);		
		}
		while(help != null && o.compareTo(help.getKey()) != 0){
			if (o.compareTo(help.getKey()) > 0){
				help = help.getRight();
				i++;
			}	
			else {
				help = help.getLeft();
				i++;
			}
		}
		if (help != null && help.getKey().compareTo(o) == 0)
			return i;
		throw new NodeNFException(nNFError + o.toString());		
	}
	
	public TreeNode<T> getParrent(T o) throws NodeNFException{
		TreeNode<T> parrent = null;
		TreeNode<T> help = super.getRoot();
		if (o == null){
			throw new NodeNFException(nNError);		
		}
		while(help != null && o.compareTo(help.getKey()) != 0 ){
			parrent = help;
			if (o.compareTo(help.getKey()) > 0)
				help = help.getRight();
			else
				help = help.getLeft();
		}
		if (help != null && help.getKey().compareTo(o) == 0)
			return parrent;
		throw new NodeNFException(nNFError + o.toString());		

		
	}


	public TreeNode<T> delete (T o) throws NodeNFException {
		TreeNode<T> parrent = null;
		TreeNode<T> help = super.getRoot();
		if (o == null){
			throw new NodeNFException(nNError);		
		}
		while(help != null && o.compareTo(help.getKey()) != 0 ){
			parrent = help;
			if (o.compareTo(help.getKey()) > 0)
				help = help.getRight();
			else
				help = help.getLeft();
		}
		if (help != null && help.getKey().compareTo(o) == 0) {
			if (help.getLeft() == null && help.getLeft() == null){
				if (parrent == null)
					super.setRoot(null);
				else{
					if (o.compareTo(parrent.getKey()) < 0)
						parrent.setLeft(null);
					else
						parrent.setRight(null);
				}	
			}
			if (help.getLeft() == null && help.getRight() != null){
				if (parrent == null)
					super.setRoot(help.getRight());	
				else{
					if (o.compareTo(parrent.getKey()) < 0)
						parrent.setLeft(help.getRight());
					else
						parrent.setRight(help.getRight());
				}	
			}

			if (help.getRight() == null && help.getLeft() != null) {
				if (parrent == null)
					super.setRoot(help.getLeft());	
				else{
					if (o.compareTo(parrent.getKey()) < 0)
						parrent.setLeft(help.getLeft());
					else
						parrent.setRight(help.getLeft());
				}	
			}
			if (help.getRight() != null && help.getLeft() != null) {
				if (parrent == null)
					super.setRoot(help.getLeft());
				else{
						if (o.compareTo(parrent.getKey()) < 0)
							parrent.setLeft(help.getLeft());
						else
							parrent.setRight(help.getLeft());
				}
				insert(help.getRight());
			}
			help.setLeft(null);
			help.setRight(null);
			return help;
		}
		throw new NodeNFException(nNFError + o.toString());				
	}
	
	public SearchTree<T> reorganize (){
		ArrayList<TreeNode<T>> list = super.inOrderList();
		SearchTree<T> n = new SearchTree<T>();
		split(n, list);
		return n;
	}
	
	private void split (SearchTree<T> n ,ArrayList<TreeNode<T>> list){
		
		
		ArrayList<TreeNode<T>> left = new ArrayList<TreeNode<T>>();
		ArrayList<TreeNode<T>> right = new ArrayList<TreeNode<T>>();
		

		int i = (list.size()  % 2 == 0) ? list.size()/2-1 : list.size()/2;
		i = (i== -1 )? 0: i;
		n.insert(list.get(i).getKey());
		for (int c = 0; c < i; c++)
			left.add(list.get(c));
		for (int c = i+1; c < list.size(); c++)
			right.add(list.get(c));
			
		if (left.size() > 0)
			split(n, left);
		if (right.size() > 0)
			split(n, right);
		
	}



	public int frequency (T el){
		TreeNode<T> i = getRoot();
		Integer freq = 0;
		if (freqtest){
			System.out.println("i: " + i + " freq " + freq);
		}
		while (i != null && i.getKey().compareTo(el) != 0){ 
			if (freqtest){
				System.out.println("i: " + i);
			}
			if (i.getKey().compareTo(el) < 0 )
				i = i.getRight();
			else
				i = i.getLeft();
		}
		if (i != null){
			freq++;
			while (i != null && i.getKey().compareTo(el) == 0){
				if (freqtest){
					System.out.println("i: " + i + " freq " + freq);
				}
				freq ++;
				i = i.getRight();
			}
		}
		
		return freq;
	}
	
	private boolean freqtest = true;
	
}
class NodeNFException extends Exception{

	private static final long serialVersionUID = -1730821238943026633L;
	NodeNFException(){}
	NodeNFException(String s){
		super(s);
	}
	
}